1. Field of the Invention
The present invention concerns a multiuser detection method and device. More particularly, the present invention concerns a maximum likelihood multiuser detection method and device for a DS-CDMA (Direct Sequence Code Division Multiple Access) telecommunication system.
2. Description of the Related Art
In a DS-CDMA mobile telecommunication system, the separation of the communications coming from or going to the different users is achieved by multiplying each complex symbol of a user by a spreading sequence which is peculiar to him, also referred to for this reason as the user signature. The spreading frequency (chip rate) being greater than the frequency of the symbols, the signal transmitted by each user is distributed (or spread) in the space of the frequencies. The ratio between the band occupied by the spread signal and the band occupied by the information signal is referred to as the spreading factor. On reception, the separation of a given user is obtained by means of a filtering adapted to the corresponding signature. When the transmission channel has a plurality of propagation paths, the output of the adapted filtering contains as many correlation peaks. Each path of the channel can be modelled by a complex multiplicative coefficient and a delay. The signals being propagated along the different paths can be aligned and combined by means of complex coefficients which are conjugates of the path coefficients, thus effecting a filtering adapted to the transmission channel. In order to simplify the terminology, the general expression “filtering adapted to the user k” will encompass both the filtering operation adapted to the signature of the user k and the filtering operation adapted to the transmission channel.
To combat the interference between signals destined for (the downlink) or coming from (the uplink) the different users, multiuser detection methods have been proposed, and notably iterative detection methods such as those known as PIC (Parallel Interference Cancellation) and SIC (Serial Interference Cancellation). They are based on the iteration of an interference elimination cycle including the estimation of the symbols transmitted, the evaluation of the interferences and their subtraction from the signals received. Although of high performance, these methods are not optimal since they do not provide an estimation in the sense of the maximum likelihood of the symbols transmitted by the different users.
A method of multiuser detection with maximum likelihood inspired by the Viterbi algorithm was proposed by S. Verdu in an article entitled “Minimum probability of error for asynchronous Gaussian multiple access channels”, published in IEEE Transactions on Information Theory, pages 85-96, January 1986, but its complexity is prohibitive since it varies exponentially with the number of users.
More recently a method of multiuser detection with maximum likelihood using a representation by a lattice of points was proposed by L. Brunel et al., in an article entitled “Euclidian space lattice decoding for joint detection in CDMA system” published in Proceedings of ITW, page 129, June 1999. According to this method, a vector characteristic of the received signal representing a statistic sufficient for the maximum likelihood detection of the symbols transmitted by the different users is determined. It is shown under certain conditions that the characteristic vector can be represented as the point in a lattice disturbed by a noise. The detection then consists of seeking the point in the lattice closest to the point corresponding to the vector received. However, the dimension of the lattice to be used generally being 2.K or K where K is the number of users, the number of points to be tested is still very high. To simplify detection, it has been proposed to limit the search for the closest neighbour to the points in the lattice belonging to a sphere centred around the point received. This simplified detection method, referred to as the “method of detection by spheres”, will be disclosed below:
The context is a multiple access mobile telecommunication system with direct sequence spectrum spreading (DS-CDMA) comprising K users communicating synchronously with a base station.
Let dk(i) be the complex symbol sent by the user k at instant i. This symbol belongs to the modulation constellation Ak used by the user k, which will also be referred to as the alphabet of symbols of the user k.
Each user k transmits a block of N symbols with an amplitude of the signal ak. The symbols are spread by a complex signature skt)=skR(t)+j.skl(t) with a duration equal to the symbol period T:sk(t)=0 if t∉└0,T└The K complex symbols dk(i)=dkR(i)+j.dkl(i) transmitted at instant i are placed in a row vector of real values d2(i) defined as:d2(i)=(d1R(i), . . . ,dKR(i),dKR(i), dKl(i))  (1)Because of the synchronisation of the users, the corresponding modulated signal can be written, as a function of the time t:
                              S          i                =                              ∑                          i              =              0                                      N              -              1                                ⁢                                    ∑                              k                =                1                            K                        ⁢                                          a                k                            ⁢                                                d                  k                                ⁡                                  (                  i                  )                                            ⁢                                                s                  k                                ⁡                                  (                                      t                    -                                          i                      ⁢                                                                                          ⁢                      T                                                        )                                                                                        (        2        )            It is assumed that the channel is an ideal channel with white additive Gaussian noise. Let rl=St+ηt be the signal received at time t and ηt a complex Gaussian noise of zero mean whose components have a variance N0.Let the row vectors be y(i)=(y1(i), . . . , yK(i)) and y2(i)=(y1R(i)y1l(i), . . . , yKR(i), ykl(i)) where yk(i)=ykR(i)+j.ykl(i) is the complex output at instant i of the filter adapted to the user k:
                                                                                          y                  k                                ⁡                                  (                  i                  )                                            ⁢                              =                Δ                            ⁢                            ⁢                                                ∫                                      -                    ∞                                                        +                    ∞                                                  ⁢                                                                            s                      k                      *                                        ⁡                                          (                                              t                        -                                                  i                          ⁢                                                                                                          ⁢                          T                                                                    )                                                        ⁢                  n                  ⁢                                      ⅆ                    t                                                                                                                          =                             ⁢                                                                    ∑                                          l                      =                      1                                        K                                    ⁢                                                            a                      l                                        ⁢                                                                  d                        l                                            ⁡                                              (                        i                        )                                                              ⁢                                                                  ∫                        0                        T                                            ⁢                                                                                                    s                            l                                                    ⁡                                                      (                            t                            )                                                                          ⁢                                                                              s                            k                            *                                                    ⁡                                                      (                            t                            )                                                                          ⁢                                                  ⅆ                          t                                                                                                                    +                                                      n                    k                                    ⁡                                      (                    i                    )                                                                                                                          =                             ⁢                                                                    ∑                                          l                      =                      1                                        K                                    ⁢                                                            a                      l                                        ⁢                                                                  d                        l                                            ⁡                                              (                        i                        )                                                              ⁢                                          R                      lk                                                                      +                                                      n                    k                                    ⁡                                      (                    i                    )                                                                                                          (        3        )            with
                    R        lk            =                                    ∫            0            T                    ⁢                                                    s                l                            ⁡                              (                t                )                                      ⁢                                          s                k                *                            ⁡                              (                t                )                                      ⁢                          ⅆ              t                                      =                              R            lk            R                    +                                    j              ·                              R                lk                I                                      ⁢                                                  ⁢            for            ⁢                                                                      ⁢                                                                    ⁢            k                                ,          l      =      1        ,    …    ⁢                  ,    K    and                    n        k            ⁡              (        i        )              =                  ∫        0        T            ⁢                                    η            i                    ·                                    s              k              *                        ⁡                          (                              t                -                                  i                  ·                  T                                            )                                      ⁢                  ⅆ          t                    The autocorrelation matrix of the spreading sequences will be denoted R(i).
If the complex elements of (3) are decomposed into their real and imaginary parts, there is obtained:
                              [                                                    y                k                R                            ⁡                              (                i                )                                      +                          j              ·                                                y                  k                  l                                ⁡                                  (                  i                  )                                                              ]                =                                            ∑                              l                =                1                            K                        ⁢                                          a                l                            ⁡                              [                                                                                                    b                        l                        R                                            ⁡                                              (                        i                        )                                                              ⁢                                          R                      lk                      R                                                        -                                                                                    b                        l                        I                                            ⁡                                              (                        i                        )                                                              ⁢                                          R                      lk                      I                                                                      ]                                              +                      j            ·                                          ∑                                  l                  =                  1                                K                            ⁢                                                a                  l                                ⁡                                  [                                                                                                              b                          l                          R                                                ⁡                                                  (                          i                          )                                                                    ⁢                                              R                        lk                        I                                                              +                                                                                            b                          l                          I                                                ⁡                                                  (                          i                          )                                                                    ⁢                                              R                        lk                        R                                                                              ]                                                              +                      [                                                            n                  k                  R                                ⁡                                  (                  i                  )                                            +                              j                ·                                                      n                    k                    I                                    ⁡                                      (                    i                    )                                                                        ]                                              (        4        )            Let.2=Diag(a1, a1, . . . , aK, aK) and R2 be the matrix of size 2K×2K such that:
                              R          2                =                  [                                                                      R                  11                  R                                                                              R                  11                  I                                                            …                                                              R                                      1                    ⁢                    K                                    R                                                                              R                                      1                    ⁢                    K                                    I                                                                                                      -                                      R                    11                    I                                                                                                R                  11                  R                                                            …                                                              -                                      R                                          1                      ⁢                      K                                        I                                                                                                R                                      1                    ⁢                    K                                    R                                                                                    ⋮                                            ⋮                                                                                                                          ⋮                                            ⋮                                                                                      R                  K1                  R                                                                              R                  K1                  I                                                            …                                                              R                  KK                  R                                                                              R                  KK                  I                                                                                                      -                                      R                    K1                    I                                                                                                R                  K1                  R                                                            …                                                              -                                      R                    KK                    I                                                                                                R                  KK                  R                                                              ]                                    (        5        )            Equation (4) can then be put in matrix form:y2(i)=d2(i)M2+n2(i)  (6)where M2 is a real matrix of size 2K×2K defined by M2=A2R2 and where the noise vector n2(i)=(n1R(i), n1l(i), . . . , nKR(i), nKl(i)) has N0R2 as its covariance matrix.
It will be demonstrated below that y2(i), as given by equation (6), can be represented as a point in a lattice Λ2 of dimension 2.K, with a generator matrix M2 corrupted by a noise n2.
The term real lattice of points Λ of dimension κ will be used for any set of vectors of R. satisfying:x=b1v1+b2v2+ . . . +b.v. where biεZ, ∀i=1, . . . , κand where {v1, v2, . . . , vκ} is a base on Rκ.
An example of a lattice of points of dimension 2 has been shown in FIG. 1.
The points in the lattice form an additive abelian sub-group of R., and it is also the smallest sub-group of Rκ containing the vectors {v1, v2, . . . , vκ} and a Z-modulus of Rκ. These base vectors form the rows of the generator matrix G for the lattice. It is therefore possible to writex=bG where b=(b1, . . . bκ)εZκ.  (7)
The region delimited by the base vectors is referred to as the fundamental parallelotope and its volume, denoted vol(Λ) and det(Λ), is referred to as the fundamental volume. This fundamental volume is none other than the modulus of the vectorial product of the κ base vectors and is therefore equal to |det(G)| where det designates the determinant. Though there are several possible choices for the generator matrix for the same lattice, on the other hand there is only one value for the fundamental volume.
The Voronoi region V or Dirichlet cell of a point x belonging to the lattice is all the points of Rκ closer to x than any other point in the lattice. The volume of this region is equal to the fundamental volume.
The stacking radius ρ of the lattice is the radius of the largest sphere inscribed in the Voronoi region and the radius of coverage that of the smallest sphere circumscribed in this same region. The stacking radius is therefore the radius of the spheres whose stacking constitutes the lattice of points and the radius of coverage is that of the smallest spheres which, centred on the points in the lattice, make it possible to cover the entire space Rκ. The density of the lattice is the ratio between the volume of the sphere of radius ρ and the fundamental volume. Finally, the coefficient of error (the kissing number) τ(Λ) of the lattice is the number of spheres tangent to one and the same sphere in the stack or, in other words, the number of neighbors of a point in the lattice, situated at the minimum distance dEmin=2ρ.
Consider once again equation (6). The complex numbers dkR(i)+j.dkl(i) belong to a finite alphabet (or constellation) A of cardinal:
                              Card          ⁡                      (            A            )                          =                              ∏                          K              =              T                        K                    ⁢                      Card            ⁡                          (                              A                k                            )                                                          (        8        )            
Assume for example that the components dkR(i) and dkl(i) are PAM modulation symbols of order M:dkR(i)ε{−M+1, −M+3, . . . , M−3, M−1}  (9)anddkl(i)ε{−M+1, −M+3, . . . , M−3, M−1}  (10)If the transformation is effected:
                                                        d              k                              ′                ⁢                                                                  ⁢                R                                      ⁡                          (              i              )                                =                                    1              2                        ⁢                          (                                                                    d                    k                    R                                    ⁡                                      (                    i                    )                                                  +                M                -                1                            )                                      ⁢                                  ⁢        and        ⁢                                  ⁢                                            d              k                              ′                ⁢                                                                  ⁢                I                                      ⁡                          (              i              )                                =                                    1              2                        ⁢                          (                                                                    d                    k                    I                                    ⁡                                      (                    i                    )                                                  +                M                -                1                            )                                      ⁢                                  ⁢                              or            ⁢                                                  ⁢            again            ⁢                                                  ⁢                          vectorially              :                                                          ⁢                                                d                  2                  ′                                ⁡                                  (                  i                  )                                                              =                                    1              2                        ⁢                          (                                                                    d                    2                                    ⁡                                      (                    i                    )                                                  +                                  v                  M                                            )                                                          (        11        )            where vM=(M−1, M−1, . . . , M−1) the components d′kR(i) and d′kl(i) are elements of Z and consequently d′2(i) is a vector of Z2K.
In general terms, if there exists an affine transformation transforming the components dkR(i) and dkl(i) into elements of Z, the vector d′2(i) can be represented by a vector of Z2K.
In a similar manner, the corresponding transformation is effected on y2(i), that is to say:
                                          y            2            ′                    ⁡                      (            i            )                          =                              1            2                    ⁢                      (                                                            y                  2                                ⁡                                  (                  i                  )                                            +                                                v                  M                                ⁢                                  M                  2                                                      )                                              (        12        )            
By means of this transformation, which is assumed to be implicit hereinafter, the vector d2(i)M2 then belongs to a lattice of points Λ2 of dimension 2.K as defined by equation (7) with G=M2. The vector y2(i) can then be considered to be a point in the lattice Λ2 corrupted by a noise n2(i).
If it is assumed that the components of the noise vector n2(i) are centred independent random Gaussian variables, the problem of detection in the sense of the maximum likelihood of the symbols transmitted by the different users amounts to a search for the point z2 in the lattice Λ2 such that its distance to y2(i) is at a minimum.
In reality, the components of the noise vector n2(i) are correlated and the covariance matrix of n2(i) is N0R2.
In order to boil down to the decorrelated case it is necessary, prior to the decoding, to effect an operation of whitening of the noise.
The matrix R being hermitian, the autocorrelation matrix R2 is symmetrical defined positive and can therefore be the subject of a Cholesky factorisation:R2=W2W2T  (13)where W2 is an inferior triangular matrix of size 2K×2K.
A whitened observation vector is defined:{tilde over (y)}2(i)=y2(i)W2T−1  (14)and a new lattice of points Ω2 consisting of vectors of components ({tilde over (x)}1R(i), {tilde over (x)}1l(i), . . . ,{tilde over (x)}KR(i), {tilde over (x)}Kl(i)) with {tilde over (x)}2(i)=x2(i)W2T−1 where x2(i) is a vector of components (x1R(i), x1l(i), . . . , xKR(i), xKl(i)) belonging to Λ2.
It can easily be shown that, after whitening, the covariance matrix of the filtered noise n2(i W2T−1 is equal to N0I2K where I2K is the identity matrix of dimension 2K. The detection therefore comprises a first step of whitening the observation vector followed by a step of seeking the closest neighbour within the lattice of points Ω2.
In order to reduce the number of points to be tested, as illustrated in FIG. 1, it is possible to limit the search to a sphere centred around the point {tilde over (y)}2. In practice, the choice of the radius of the sphere results from a compromise: it must not be too large in order not to lead to an excessively high number of points and sufficiently large to include at least the closest neighbour.
FIG. 2 depicts schematically a multiuser detection device using a method of detection by spheres. The received signal n is filtered by a battery of filters adapted to each of the users, 2101, . . . , 210K. The real and imaginary components of the observation vector y2(i) output from the adapted filters are transmitted to a matrix calculation unit performing the spectral whitening operation according to equation (14). The real and imaginary components of the whitened vector {tilde over (y)}2(i) are then transmitted to a unit for detection by spheres seeking the closest neighbour of the point received within the lattice Ω2 of dimension 2.K. The coordinates of the closest neighbour directly give the real and imaginary components of the estimated symbols {circumflex over (d)}k(i) for the different users.
It can be shown that the method of detection by spheres as disclosed above has a complexity in terms of O(K6) which may prove very disadvantageous when the number of users is high.